package QuickSort;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 均先生
 * Date: 2023-10-16
 * Time: 19:01
 */
public class QuickSort {
    public void quickSort(int[] array,int start,int end) {
        if (start < end) {
            int q = PARTITION(array,start,end);
            quickSort(array,start,q-1);
            quickSort(array,q+1,end);
        }
    }

    private int PARTITION(int[] array, int start, int end) {
        int x = array[end];
        int pointer = start-1;
        ;
        for (int j = start; j < end; j++) {
            if (array[j] <= x) {
                pointer++;
                swap(array,pointer,j);
            }
        }
        swap(array,pointer+1,end);
        return pointer+1;
    }

    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
